1. Field of the Invention
The invention relates to field-programmable gate array (FPGA) devices. More specifically, the invention is a routing system for reducing signal skew in an FPGA.
2. Background
FPGAs are known in the art. An FPGA comprises any number of logic modules, a routing architecture and programmable elements that may be programmed to selectively interconnect the logic modules to one another and to define the functions of the logic modules. An FPGA is an array of uncommitted gates with uncommitted wiring channels. To implement a particular circuit function, a user circuit is mapped into an array and the wiring channels' appropriate connections are programmed to implement the necessary wiring connections that form the user circuit.
A field programmable gate array circuit can be programmed to implement virtually any set of logic functions. Input signals are processed by the programmed circuit to produce the desired set of outputs. Such inputs flow from a user's system, through input buffers and through the circuit, and finally back out the user's system via output buffers. Such buffers may provide any or all of the following input/output (I/O) functions: voltage gain, current gain, level translation, delay, signal isolation or hysteresis.
An FPGA core tile (tile) may be employed as a stand-alone FPGA, repeated in a rectangular array of tiles, or included with other devices in a system-on-a-chip (SOC). A tile is the basic building block consisting of a logic module and routing resources. An Array of tiles may also be known as a tile. An FPGA tile may also include other components such as read only memory (ROM) modules or random access memory (RAM) modules. Horizontal and vertical routing channels provide interconnections between the various components within an FPGA tile. Connections are provided by programmable elements that form connections between the routing resources.
The programmable elements (cells or switches) in an FPGA can be either one-time programmable or re-programmable. Re-programmable elements used in FPGA technologies may comprise volatile or non-volatile transistors or other re-programmable elements as is well known to those of ordinary skill in the art. One-time programmable elements used in FPGA technologies may comprise antifuse devices.
Edge-triggered storage devices, for example a flip-flops (FFs), within an FPGA may be affected by skew. Skew is the difference in arrival time at two different points for a signal from a common origin, due in part to delay caused by devices that the signal previously passed through. Delay of the clock or clock-enable for each device and throughout a system is one cause of skew.
During design of a user circuit to be implemented in the programmable logic of an FPGA, one objective is to avoid a situation called “shoot-through.” Shoot-through occurs when a circuit receives a signal and propagates that signal to the next circuit before the next circuit is ready to receive that signal, according to a desired sequence of signals. The user circuit implemented in the FPGA will not function properly if shoot-through occurs, and shoot-through is more likely to occur when the skew is high on the signal or signals which control the sequence. Shoot-through typically occurs in pipelines or shift registers, but may also occur in a chain of latches where each latch is transparent on opposite values of the enabling signal. Furthermore, high skew may degrade the performance of a user circuit implemented in an FPGA by requiring a waiting period until a signal arrives. Shoot-through on an edge-triggered device cannot be corrected by changing the frequency of the triggering signal.
Fan-out is the number of destinations a signal will reach from a given origin. When a signal will eventually arrive at many different destinations, there is high fan-out. Many circuit designs include high fan-out signals and also high skew, which constrains circuit design in order to avoid shoot-though and other timing errors. Fan-out is a function of the number of destinations to which a signal may propagate, while skew is a function of the difference in arrival time at two different points from a common origin.
High fan-out routing resources are conductors that span a significant number of tiles and are, in combination, capable of carrying signals to substantially any location on a programmable logic device, from any insertion point on the high fan-out routing resource. While the number of insertion points may be limited, insertion points may be reached through ordinary routing resources, and therefore substantially any location on the programmable logic device may be reached from substantially any other location on the programmable logic device, in an efficient manner (i.e., with low insertion delay and low skew) via high fan-out routing resources. High fan-out routing lines are typically much longer than general (inter- and intra-tile) local routing lines. Because of their efficiency and flexibility, high fan-out resources are highly prized by designers who configure programmable logic devices to implement logic functions. High fan-out signals are signals that are distributed to a high number of locations (“landing points”) on a device. Typical examples of high fan-out signals requiring high fan-out routing resources are control signals such as clock signals and reset signals. Some data signals may also require high fan-out routing resources.
As FPGAs grow in size, on-chip clock distribution becomes increasingly important. Skew and delay impact FPGA performance and the task of managing skew and delay with conventional means becomes more difficult in large FPGAs.
FIG. 1 is a diagram illustrating a prior art block of FPGA tiles. Tile block 100 is a simplified diagram of a block of FPGA core tiles 110 extending horizontally and vertically in an array.
A tile is a basic unit of programmable logic that includes logic modules and routing resources. In one embodiment, a tile can be configured as a register or a look-up table (“LUT”). In another embodiment, a tile could contain multiple registers and LUTs. Tiles 110, sets of routing resources, or conductors (not shown), and sets of user programmable switches or cells (not shown) associated with both tiles 110 and the routing interconnects are included in the FPGA circuit. When these switches are properly programmed (set to on or off states), tiles 110 and the interconnects of the FPGA are customized or configured to perform specific functions. By reprogramming the on-off states of these switches, an FPGA can perform different functions. Once a specific configuration of an FPGA has been decided upon, it can be configured to perform the function dictated by the configuration. Tiles 110 are, for example, FPGA core tiles that perform functions and may be configured together in various ways in order to implement some overall function or functions within the FPGA. Routing resources, or conductors, connect the tiles into multiple blocks, for example tile block 100 is comprised of multiple tiles, or configurable logic blocks, connected by local routing resources. In a typical FPGA chip there are multiple tile blocks connected together, with conductors connecting the various blocks. Although “connect” and variants are used throughout the specification, one of ordinary skill in the art will recognize that many of the interconnections are programmable and not conducting links until the respective programmable elements are activated. “Connect” and “connected” as used in this disclosure may refer to objects that are physically connected as well as programmably connected or connectable or capable of being connected.
Although many different configurations are possible, one typical example of a block 100 includes a horizontal plurality of sixteen tiles and vertical plurality of twelve tiles, for a total block array size of 16×12=192 tiles 110.
FIG. 2 is a diagram illustrating interconnectivity between two prior art tile blocks of FIG. 1. In FIG. 2, tile blocks 100 include tiles 110 arranged in rows and columns. Each tile in a row of tiles is connectable to each other tile in the row via rows of horizontal regional row conductors (rows) 200. Each horizontal regional row conductor 200 of the tile blocks shown in FIG. 2 is connected (i.e., capable of being connected) to regional vertical conductor 210 (a vertical regional routing resource or spine). Regional vertical conductor 210 extends past many tile blocks. Signal flow is typically unidirectional, for example a signal may only flow from global horizontal conductor 220 to regional vertical conductor 210 and on to one of regional horizontal conductors 200, but not in the other direction. On a unidirectional routing line, the signal may only flow in one direction, from sources to loads. Some programmable logic devices may employ bi-directional routing lines where signals can flow in either direction along the line, depending on how the user circuit is implemented. A signal is typically inserted at the juncture of two routing resources, for example a signal from tile 110-1 may be inserted on to regional vertical conductor 210 and is capable of propagating to all tiles reachable from that conductor.
Global horizontal conductor (rib) 220 provides a signal source for all intersecting regional vertical conductors 210. Global, national, and regional conductors are high fan-out routing resources and are sometimes collectively referred to in the art as “global” routing resources or “global” routing conductors because they are part of the signal routing system that spans multiple tile blocks, even though they do not all span substantially the entire array of tile blocks, as do true “global” conductors. In the present disclosure, “global” generally refers to conductors that span substantially all of the array of tile blocks, but may in certain cases be used to refer to a system of high fan-out routing lines distinguished from low fan-out “local” routing lines, as will be clear from the context.
FIG. 3 is a diagram illustrating interconnectivity between two prior art tile blocks of FIG. 1. In FIG. 3, tile blocks 100 are adjacent to global horizontal conductor 220 and adjacent to regional vertical conductors 210. Each adjacent block 100 separated by a global horizontal conductor 220 has tiles 110 connectable directly to one another by local vertical conductors 300. Block 100-1 has tiles 110 which are connectable to each other and, to varying degrees, to tiles 110 in block 100-2 by local vertical conductors 300. For example, tile 110-1 is directly connectable to tiles 110-2, 110-3 and 110-4 by local vertical conductor 300-1. Tile 110-2 is directly connectable to tiles 110-3, 110-4, and 110-5 by local vertical conductor 300-3. Tile 110-3 is directly connectable to tile 110-4 by local vertical conductor 300-2 and to tiles 110-4, 110-5 and 110-6 by local vertical conductor 300-4. As used in this disclosure, the term “local” is used to identify conductors that only span limited areas and are not part of the high fan-out routing hierarchy. These routing conductors are also referred to as “regular” or “ordinary” routing resources. Although it is possible in some devices to connect enough of these ordinary routing lines to span an entire programmable logic device, a path that long and that passes through many programmable cells or switches would be highly inefficient (i.e., have high skew and high insertion delay). Typically, local conductors do not span an entire row or column of tiles in a block, but may in some instances.
There are typically areas of electrical isolation that separate certain tile blocks and routing resources. For example, vertical areas of electrical isolation may run between columns of the blocks that are not connected to each other via regional horizontal conductors.
Regional horizontal row conductors 200 are typically high fan-out (sometimes referred to as “global”) routing resources and local vertical conductors 300 are general routing resources having low fan-out and high skew, necessitating careful circuit design. The fan-out dependent delay and skew of nets that employ principally local routing resources is not predictable. High fan-out routing resources, on the other hand, have predictable delay and skew. The primary use of high-fanout, low-skew routing resources is to route signals that have whole-chip fan-out (or reach) and need to be low-skew. For example, clock signals and reset signals, which may have thousands of loads, are good candidates for routing and distribution via high fan-out resources. Although prior signal routing schemes in programmable logic devices have provided both local routing resources and high fan-out routing resources for local and global signal distribution in the programmable logic devices, there has not been a mechanism for efficiently aggregating high fan-out routing resources to allow their use in local distribution of local signals when not needed for global signal distribution.